package com.zpself.module.算法练习.算法.动态规划;

import java.util.HashSet;
import java.util.Set;

/**
 * @author By ZengPeng
 * @Description
 * @date in  2020/10/10 10:25
 * @Modified By
 */
public class 最大公共子串 {
    static Set<String> result = new HashSet<>();
    public static void main(String[] args) {
        System.out.println("最大公共子串长度为:"+getPublicString("BDCABA","ABCBDAB"));
    }

    private static int getPublicString(String strA, String strB) {
        char[] A = strA.toCharArray();
        char[] B = strB.toCharArray();
        int[][] dp = new int[A.length+1][B.length+1];
        //dp
        for(int i = 0; i < A.length+1; i++){
            for(int j = 0; j < B.length+1; j++){
                if (i == 0 || j == 0){
                    dp[i][j] = 0;
                    continue;
                }
                if (A[i-1] ==  B[j-1]){
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }else{
                    dp[i][j] =0;
                }
            }

        }
        //打印表格
        int max=0;
        for(int i = 0; i < A.length+1; i++){
            for(int j = 0; j < B.length+1; j++){
                max = Math.max(max,dp[i ][j ]);
                System.out.print(dp[i][j]);
            }
            System.out.println();
        }
        return max;
    }
}
